package th.retrofit.lib;

final class Solution79 {

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        if (m == 0 || board[0] == null) return false;
        int n = board[0].length;
        if (n == 0 || m *n < word.length()) return false;
        boolean[][] used = new boolean[m][n];
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (backtrack(board, used, i, j, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(char[][] board, boolean[][] used, int i, int j, String word) {
        int m = board.length;
        int n = board[0].length;
        char target = word.charAt(0);
        if (i < 0 || j< 0 || i >= m || j >= n) return false;
        if (word.length() == 1) return board[i][j] == target;
        if (target != board[i][j]) return false;
        boolean result = false;
        if (i - 1 >= 0 && !used[i - 1][j]) {
            used[i - 1][j] = true;
            result = backtrack(board, used, i - 1, j, word.substring(1));
            if (result) return true;
            used[i - 1][j] = false;
        }
        if (i + 1 < m && !used[i + 1][j]) {
            used[i + 1][j] = true;
            result = backtrack(board, used, i + 1, j, word.substring(1));
            if (result) return true;
            used[i + 1][j] = false;
        }
        if (j - 1 >= 0 && !used[i][j - 1]) {
            used[i][j - 1] = true;
            result = backtrack(board, used, i, j - 1, word.substring(1));
            if (result) return true;
            used[i][j - 1] = false;
        }
        if (j + 1 < n && !used[i][j + 1]) {
            used[i][j + 1] = true;
            result = backtrack(board, used, i, j + 1, word.substring(1));
            if (result) return true;
            used[i][j + 1] = false;
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };
        String word = "EES";
        System.out.println(new Solution79().exist(board, word));
    }

}
